package leetcode.hot100;

public class Solution309 {
//最佳买卖股票时机含冷冻期

    public static void main(String[] args) {

        int[] prices = {1,2,3,0,2};
        System.out.println(new Solution309().maxProfit(prices));

    }

    public int maxProfit(int[] prices) {
        //每天结束时只可能处于3种状态：有股票0，无股票被冻结1，无股票无冻结2
        //dp[i][j]代表第i天以状态j结束时的最大收益
        int[][] dp = new int[prices.length+1][3];
        dp[0][0] = -prices[0];
        for (int i = 1; i < dp.length; i++) {
            //dp[i][0] = max(dp[i-1][2]-prices[i-1]当天买的,dp[i-1][0]前一天买的)
            //dp[i][1] = dp[i-1]+prices[i-1]当天卖的
            //dp[i][2] = max(dp[i-1][1]前一天卖了,dp[i-1][2]前一天也是无股票无冻结)
            dp[i][0] = Math.max(dp[i-1][2]-prices[i-1],dp[i-1][0]);
            dp[i][1] = dp[i-1][0]+prices[i-1];
            dp[i][2] = Math.max(dp[i-1][1],dp[i-1][2]);
        }
        return Math.max(dp[dp.length-1][1],dp[dp.length-1][2]);
    }


}
